7125. Васин круг

Вася выписал n букв "X" и "E" по кругу. Вася подумал, что получится 2n вариантов сделать это, так как каждая буква может быть либо "X", либо "E". Однако Петя заметил, что некоторые различные последовательности букв могут быть преобразованы друг в друга циклическим сдвигом (таким образом представляя одну и ту же циклическую строку).

Например, строки "XXE"-"XEX"-"EXX" на самом деле одинаковы.

Петя хочет знать, сколько существует различных циклических строк из n букв. Помогите ему это узнать.

Вход. Одно число n (1 ≤ n ≤ 200000).

Выход. Вывести количество циклических строк длины n.

Пример входа

3

Пример выхода

4

РЕШЕНИЕ

Теорема Пойа

Анализ алгоритма

Требуется найти количество ожерелий из n бусинок, которые можно получить в результате раскрашивания двумя красками (красками здесь являются буквы "X" и "E").

Если ожерелье имеет n бусинок, каждая из которых может быть покрашена в один из k цветов, то количество различных ожерелий равно

Реализация алгоритма

Поскольку n ≤ 200000, то ответ будет большим числом. Воспользуемся длинной арифметикой.

import java.util.*;

import java.math.*;

public class Main

{

Вычисление функции Эйлера φ(n).

static long euler(long n)

{

long result = n;

for(int i = 2; i <= Math.sqrt(n);i++)

{

if (n % i == 0) result -= result / i;

while (n % i == 0) n /= i;

}

if (n > 1) result -= result / n;

return result;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

BigInteger res = new BigInteger("0");

Установим переменную k равной количеству цветов.

BigInteger k = new BigInteger("2");

int i, sq, n = con.nextInt();

int up = sq = (int)Math.sqrt(n);

if (sq * sq == n) up--;

Перебираем делители i числа n от 1 до . Если i – делитель n, то n / i также будет делителем n.

for(i = 1; i <= up; i++)

if (n % i == 0)

{

res = res.add(k.pow(n/i).multiply(BigInteger.valueOf(euler(i))));

res = res.add(k.pow(i).multiply(BigInteger.valueOf(euler(n/i))));

}

Отдельно обработаем случай, если n является полным квадратом.

if (sq * sq == n)

res = res.add(k.pow(i).multiply(BigInteger.valueOf(euler(i))));

res = res.divide(BigInteger.valueOf(n));

Выводим искомый ответ.

System.out.println(res);

}

}